<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/favicon.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/@fortawesome/fontawesome-free@6.7.2/css/all.min.css" integrity="sha256-dABdfBfUoC8vJUBOwGVdm8L9qlMWaHTIfXt+7GnZCIo=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"blog.csgrandeur.cn","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.22.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"copycode":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"top_n_per_article":1,"unescape":false,"preload":false,"trigger":"auto"}}</script><script src="/js/config.js"></script>

    <meta name="description" content="组合数学入门">
<meta property="og:type" content="article">
<meta property="og:title" content="36.组合数学入门">
<meta property="og:url" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/index.html">
<meta property="og:site_name" content="CSGrandeur&#39;s Thinking">
<meta property="og:description" content="组合数学入门">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E7%A2%9F%E5%AD%90%E7%9D%80%E8%89%B2.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92_%E7%BB%B4%E5%BA%A6%E6%89%A9%E5%B1%95.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%A0%BC%E8%B7%AF%E5%BE%84.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/nim%E6%B8%B8%E6%88%8F_k%E5%A0%86.svg">
<meta property="article:published_time" content="2025-06-18T08:05:35.000Z">
<meta property="article:modified_time" content="2025-06-26T11:06:02.066Z">
<meta property="article:author" content="CSGrandeur">
<meta property="article:tag" content="ACM">
<meta property="article:tag" content="Algorithm">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E7%A2%9F%E5%AD%90%E7%9D%80%E8%89%B2.svg">


<link rel="canonical" href="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/">


<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/","path":"2025-06-18-36-组合数学入门/","title":"36.组合数学入门"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>36.组合数学入门 | CSGrandeur's Thinking</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?7958adf931092425a489778560129144"></script>







  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">CSGrandeur's Thinking</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">Cogito Ergo Sum</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
      <div class="search-header">
        <span class="search-icon">
          <i class="fa fa-search"></i>
        </span>
        <div class="search-input-container">
          <input autocomplete="off" autocapitalize="off" maxlength="80"
                placeholder="搜索..." spellcheck="false"
                type="search" class="search-input">
        </div>
        <span class="popup-btn-close" role="button">
          <i class="fa fa-times-circle"></i>
        </span>
      </div>
      <div class="search-result-container">
        <div class="search-result-icon">
          <i class="fa fa-spinner fa-pulse fa-5x"></i>
        </div>
      </div>
    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8"><span class="nav-number">1.</span> <span class="nav-text">组合数学入门</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%B8%BD%E5%B7%A2%E5%8E%9F%E7%90%86"><span class="nav-number">1.1.</span> <span class="nav-text">鸽巢原理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E9%B8%BD%E5%B7%A2%E5%8E%9F%E7%90%86"><span class="nav-number">1.1.1.</span> <span class="nav-text">基本鸽巢原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%9E%E7%BB%AD%E5%92%8C%E6%95%B4%E9%99%A4%E9%97%AE%E9%A2%98"><span class="nav-number">1.1.2.</span> <span class="nav-text">连续和整除问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E5%A4%A7%E5%B8%88%E9%97%AE%E9%A2%98"><span class="nav-number">1.1.3.</span> <span class="nav-text">国际象棋大师问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%8A%A0%E5%BC%BA%E7%89%88%E9%B8%BD%E5%B7%A2%E5%8E%9F%E7%90%86"><span class="nav-number">1.1.4.</span> <span class="nav-text">加强版鸽巢原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%A2%9F%E5%AD%90%E7%9D%80%E8%89%B2%E9%97%AE%E9%A2%98"><span class="nav-number">1.1.5.</span> <span class="nav-text">碟子着色问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%BA%8F%E5%88%97%E5%8D%95%E8%B0%83%E5%AD%90%E5%BA%8F%E5%88%97"><span class="nav-number">1.1.6.</span> <span class="nav-text">序列单调子序列</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E9%A1%B9%E5%BC%8F%E7%B3%BB%E6%95%B0"><span class="nav-number">1.2.</span> <span class="nav-text">二项式系数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E5%AE%9A%E4%B9%89"><span class="nav-number">1.2.1.</span> <span class="nav-text">基本定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%B8%95%E6%96%AF%E5%8D%A1%E4%B8%89%E8%A7%92"><span class="nav-number">1.2.2.</span> <span class="nav-text">杨辉三角&#x2F;帕斯卡三角</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E9%A1%B9%E5%BC%8F%E5%AE%9A%E7%90%86"><span class="nav-number">1.2.3.</span> <span class="nav-text">二项式定理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%AE%9A%E7%90%86"><span class="nav-number">1.2.4.</span> <span class="nav-text">多项式定理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%BB%84%E5%90%88%E6%95%B0%E9%80%92%E6%8E%A8"><span class="nav-number">1.2.5.</span> <span class="nav-text">组合数递推</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%89%B9%E6%AE%8A%E8%AE%A1%E6%95%B0%E5%BA%8F%E5%88%97%E7%A7%91%E6%99%AE"><span class="nav-number">1.3.</span> <span class="nav-text">特殊计数序列科普</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0catalan-numbers"><span class="nav-number">1.3.1.</span> <span class="nav-text">卡特兰数（Catalan Numbers）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%AC%AC%E4%BA%8C%E7%B1%BB%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0stirling-numbers-of-the-second-kind"><span class="nav-number">1.3.2.</span> <span class="nav-text">第二类斯特林数（Stirling
Numbers of the Second Kind）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%B4%9D%E5%B0%94%E6%95%B0bell-numbers"><span class="nav-number">1.3.3.</span> <span class="nav-text">贝尔数（Bell Numbers）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%AC%AC%E4%B8%80%E7%B1%BB%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0stirling-numbers-of-the-first-kind"><span class="nav-number">1.3.4.</span> <span class="nav-text">第一类斯特林数（Stirling
Numbers of the First Kind）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A4%A7schroder%E6%95%B0%E4%B8%8E%E5%B0%8Fschroder%E6%95%B0"><span class="nav-number">1.3.5.</span> <span class="nav-text">大Schroder数与小Schroder数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%80%BB%E7%BB%93%E8%A1%A8%E6%A0%BC"><span class="nav-number">1.3.6.</span> <span class="nav-text">总结表格</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#nim-%E6%B8%B8%E6%88%8F"><span class="nav-number">1.4.</span> <span class="nav-text">Nim 游戏</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A0%86-nim-%E6%B8%B8%E6%88%8F%E7%9A%84%E7%AD%96%E7%95%A5"><span class="nav-number">1.4.1.</span> <span class="nav-text">2 堆 Nim 游戏的策略</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%80%9A%E7%94%A8-k--%E5%A0%86-nim-%E6%B8%B8%E6%88%8F%E7%9A%84%E7%AD%96%E7%95%A5"><span class="nav-number">1.4.2.</span> <span class="nav-text">通用 $ k $-堆 Nim 游戏的策略</span></a></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">CSGrandeur</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">72</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">6</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">22</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://blog.csgrandeur.cn/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="CSGrandeur">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="36.组合数学入门 | CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          36.组合数学入门
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2025-06-18 16:05:35" itemprop="dateCreated datePublished" datetime="2025-06-18T16:05:35+08:00">2025-06-18</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2025-06-26 19:06:02" itemprop="dateModified" datetime="2025-06-26T19:06:02+08:00">2025-06-26</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/" itemprop="url" rel="index"><span itemprop="name">ACM</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/ACMCOURSE/" itemprop="url" rel="index"><span itemprop="name">ACMCOURSE</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody"><h1 id="组合数学入门">组合数学入门</h1>
<span id="more"></span>
<h2 id="鸽巢原理">鸽巢原理</h2>
<h3 id="基本鸽巢原理">基本鸽巢原理</h3>
<p><strong>定理</strong>：将 <span class="math inline">\(n+1\)</span>
个物体放入 <span class="math inline">\(n\)</span>
个盒子中，至少有一个盒子包含不少于两个物体。</p>
<p><strong>证明</strong>（反证法）：</p>
<p>假设每个盒子最多只有一个物体，那么 <span
class="math inline">\(n\)</span> 个盒子最多只能装 <span
class="math inline">\(n\)</span> 个物体，与有 <span
class="math inline">\(n+1\)</span>
个物体矛盾。因此至少有一个盒子有两个或更多物体。</p>
<p><strong>经典应用</strong>：</p>
<ol type="1">
<li>13个人中至少有两个人生日在同一个月</li>
<li>从<span class="math inline">\(n\)</span>对夫妇中选<span
class="math inline">\(n+1\)</span>人时，必选到一对夫妻</li>
</ol>
<h3 id="连续和整除问题">连续和整除问题</h3>
<p><strong>问题</strong>：给定<span
class="math inline">\(m\)</span>个整数<span
class="math inline">\(a_1,a_2,...,a_m\)</span>，必存在连续若干数之和能被<span
class="math inline">\(m\)</span>整除。</p>
<p><strong>证明思路</strong>：</p>
<ol type="1">
<li>考虑前<span class="math inline">\(k\)</span>项和<span
class="math inline">\(S_k = a_1+...+a_k\)</span>（<span
class="math inline">\(m\)</span>个数共<span
class="math inline">\(m\)</span>种前缀和）</li>
<li>如果某个<span class="math inline">\(S_k\)</span>能被<span
class="math inline">\(m\)</span>整除，得证</li>
<li>否则，这些和除以<span
class="math inline">\(m\)</span>的余数只能是<span
class="math inline">\(1,...,m-1\)</span>（<span
class="math inline">\(m-1\)</span> 种余数）</li>
<li>由鸽巢原理，必有两个和余数相同，比如<span
class="math inline">\(S_i\)</span>和<span
class="math inline">\(S_j\)</span></li>
<li>则<span class="math inline">\(S_j-S_i =
a_{i+1}+...+a_j\)</span>能被<span
class="math inline">\(m\)</span>整除</li>
</ol>
<p><strong>例子</strong>：数列2,4,6,3,5,5,6中，6+3+5=14能被7整除。</p>
<h3 id="国际象棋大师问题">国际象棋大师问题</h3>
<p><strong>问题</strong>：11周（77天）内每天至少下一盘棋，每周不超过12盘。证明存在连续若干天共下21盘。</p>
<p><strong>证明要点</strong>：</p>
<ol type="1">
<li>设<span class="math inline">\(a_i\)</span>为前<span
class="math inline">\(i\)</span>天的总盘数，形成严格递增序列</li>
<li>总盘数<span class="math inline">\(a_{77} \leq 12×11 =
132\)</span></li>
<li>考虑序列<span class="math inline">\(a_1,...,a_{77}\)</span>和<span
class="math inline">\(a_1+21,a_{2}+21,...,a_{77}+21 \leq
132+21=153\)</span>（共154个数）</li>
<li>这些数都在1到153之间，但有154个数，必有相等</li>
<li>只能是某个<span class="math inline">\(a_i = a_j
+21\)</span>，即第<span class="math inline">\(j+1\)</span>到<span
class="math inline">\(i\)</span>天共下<span
class="math inline">\(a_{i}-a_{j}=21\)</span>盘</li>
</ol>
<h3 id="加强版鸽巢原理">加强版鸽巢原理</h3>
<p><strong>定理</strong>：将<span class="math inline">\(q_1+q_2+...+q_n
-n+1\)</span>个物体放入<span
class="math inline">\(n\)</span>个盒子，无论什么顺序放好后，盒子编号为<span
class="math inline">\(1\sim n\)</span>，则至少有一个特定的数字<span
class="math inline">\(i\)</span>，编号为 <span
class="math inline">\(i\)</span> 的盒子包含不少于<span
class="math inline">\(q_i\)</span>个物体。</p>
<p><strong>证明</strong>：</p>
<ol type="1">
<li><p>假设每个盒子<span class="math inline">\(i\)</span>都含有少于<span
class="math inline">\(q_i\)</span>个物体，即最多有<span
class="math inline">\(q_{i}-1\)</span>个</p></li>
<li><p>则所有盒子中的物体总数不超过：</p>
<p><span
class="math display">\[(q_1-1)+(q_2-1)+...+(q_n-1)=q_1+q_2+...+q_n-n\]</span></p></li>
<li><p>但实际放入的物体数为<span
class="math inline">\(q_1+q_2+...+q_n-n+1\)</span>个</p></li>
<li><p>这与假设矛盾，因此至少存在一个盒子<span
class="math inline">\(i\)</span>含有不少于<span
class="math inline">\(q_i\)</span>个物体</p></li>
</ol>
<p><strong>注</strong>：当放入<span
class="math inline">\(q_1+q_2+...+q_n-n\)</span>个物体时，可以使得每个盒子<span
class="math inline">\(i\)</span>都恰好含有<span
class="math inline">\(q_i-1\)</span>个物体，剩下一个就面对的基本窠巢原理。</p>
<p><strong style="color:red">推论（平均原理）</strong>：</p>
<ol type="1">
<li><p>若<span class="math inline">\(n\)</span>个非负整数<span
class="math inline">\(m_1,m_2,...,m_n\)</span>的平均数大于<span
class="math inline">\(r-1\)</span>，即<br />
<span class="math display">\[\frac{m_1+m_2+...+m_n}{n} &gt;
r-1\]</span><br />
<strong>则至少有一个整数大于或等于<span
class="math inline">\(r\)</span></strong></p></li>
<li><p>若<span class="math inline">\(n\)</span>个非负整数<span
class="math inline">\(m_1,m_2,...,m_n\)</span>的平均数小于<span
class="math inline">\(r+1\)</span>，即<br />
<span class="math display">\[\frac{m_1+m_2+...+m_n}{n} &lt;
r+1\]</span><br />
<strong>则至少有一个整数小于<span
class="math inline">\(r+1\)</span></strong></p></li>
</ol>
<h3 id="碟子着色问题">碟子着色问题</h3>
<p><strong>问题</strong>：两个分成200扇形的碟子，大碟子红蓝各100个，小碟子任意着色。证明存在对齐方式使至少100个扇形颜色匹配。</p>
<img src="/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E7%A2%9F%E5%AD%90%E7%9D%80%E8%89%B2.svg" class="">
<p><strong>证明要点</strong>：</p>
<ol type="1">
<li>固定大碟子，小碟子有<span
class="math inline">\(200\)</span>种可能位置</li>
<li>每个扇形在<span
class="math inline">\(100\)</span>个位置上会与大碟子同色</li>
<li>总匹配次数=<span class="math inline">\(200\times
100=20000\)</span></li>
<li>平均每个位置有<span class="math inline">\(100\)</span>次匹配（即均值
<span class="math inline">\(&gt;99\)</span>）</li>
<li>由平均原理，存在位置匹配数 <span class="math inline">\(\geq
100\)</span></li>
</ol>
<h3 id="序列单调子序列">序列单调子序列</h3>
<p><strong>定理</strong>：任意<span
class="math inline">\(n^2+1\)</span>个数的序列必存在长度为<span
class="math inline">\(n+1\)</span>的单调（非增或非减）子序列。</p>
<p><strong>证明思路</strong>：</p>
<ol type="1">
<li>对每个数<span class="math inline">\(a_k\)</span>，记<span
class="math inline">\(m_k\)</span>为从它开始的最长非减序列长度</li>
<li>若某个<span class="math inline">\(m_k\geq
n+1\)</span>，则存在所需非减序列</li>
<li>否则所有<span class="math inline">\(m_k\leq
n\)</span>，由鸽巢原理至少有<span
class="math inline">\(n+1\)</span>个<span
class="math inline">\(m_k\)</span>相等</li>
<li>则这<span class="math inline">\(n+1\)</span>个<span
class="math inline">\(k_{i}\)</span>位置的数必须非增关系
反证：如果它们不是非增关系，则存在 <span class="math inline">\(i&lt;j,
a_{i}&lt;a_{j}\)</span>，<span class="math inline">\(a_{i}\)</span>放在
<span class="math inline">\(a_{j}\)</span>前面可以构成一个比 <span
class="math inline">\(m_{k}\)</span> 更长的非减序列，与<span
class="math inline">\(m_{i}=m_{j}=m_{k}\)</span>产生矛盾</li>
</ol>
<h2 id="二项式系数">二项式系数</h2>
<h3 id="基本定义">基本定义</h3>
<p>二项式系数<span
class="math inline">\(\binom{n}{k}\)</span>的定义：</p>
<ol type="1">
<li>当<span class="math inline">\(k &gt; n\)</span>时，<span
class="math inline">\(\binom{n}{k} = 0\)</span></li>
<li>当<span class="math inline">\(k = 0\)</span>时，<span
class="math inline">\(\binom{n}{0} = 1\)</span></li>
<li>当<span class="math inline">\(1 \leq k \leq n\)</span>时，<span
class="math inline">\(\binom{n}{k} = \frac{n!}{k!(n-k)!} =
\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}\)</span></li>
</ol>
<p>二项式系数 <span class="math inline">\(\binom{n}{k}\)</span>
等于组合数 <span class="math inline">\(C_n^k\)</span></p>
<p><strong>性质</strong>：</p>
<ul>
<li>对称性：<span class="math inline">\(\binom{n}{k} =
\binom{n}{n-k}\)</span>（当<span class="math inline">\(0 \leq k \leq
n\)</span>时）</li>
<li><strong style="color:red">帕斯卡公式</strong>：<span
class="math inline">\(\binom{n}{k} = \binom{n-1}{k} +
\binom{n-1}{k-1}\)</span></li>
</ul>
<h3 id="杨辉三角帕斯卡三角">杨辉三角/帕斯卡三角</h3>
<img src="/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92.svg" class="">
<p>杨辉三角中的数具有以下特点：</p>
<ol type="1">
<li>边界上的数都是<span class="math inline">\(1\)</span></li>
<li>其他数等于其上方和左上方两个数之和</li>
<li>第<span class="math inline">\(n\)</span>行的和为<span
class="math inline">\(2^n\)</span>，即<strong style="color:red"><span
class="math inline">\(\sum_{k=0}^n \binom{n}{k} =
2^n\)</span></strong></li>
</ol>
<img src="/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92_%E7%BB%B4%E5%BA%A6%E6%89%A9%E5%B1%95.svg" class="">
<p><strong>特殊数列</strong>：</p>
<ul>
<li>第1列：<span class="math inline">\(\binom{n}{1} =
n\)</span>（计数数）</li>
<li>第2列：<span class="math inline">\(\binom{n}{2} =
\frac{n(n-1)}{2}\)</span>（三角形数）</li>
<li>第3列：<span class="math inline">\(\binom{n}{3} =
\frac{n(n-1)(n-2)}{3!}\)</span>（四面体数）</li>
</ul>
<h3 id="二项式定理">二项式定理</h3>
<p><strong>定理</strong>：设<span
class="math inline">\(n\)</span>为正整数，对所有的<span
class="math inline">\(x\)</span>和<span
class="math inline">\(y\)</span>，有：</p>
<p><span class="math display">\[(x+y)^n = \sum_{k=0}^n
\binom{n}{k}x^{n-k}y^k\]</span></p>
<p><strong>等价形式</strong>：</p>
<ol type="1">
<li><span class="math inline">\((x+y)^n = \sum_{k=0}^n
\binom{n}{n-k}x^{n-k}y^k\)</span></li>
<li><span class="math inline">\((x+y)^n = \sum_{k=0}^n
\binom{n}{n-k}x^ky^{n-k}\)</span></li>
<li><span class="math inline">\((x+y)^n = \sum_{k=0}^n
\binom{n}{k}x^ky^{n-k}\)</span></li>
</ol>
<p><strong>特殊情况</strong>：</p>
<ul>
<li><span class="math inline">\((1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k =
\sum_{k=0}^n \binom{n}{n-k}x^k\)</span></li>
</ul>
<p><strong>常见展开式</strong>：</p>
<ul>
<li><span class="math inline">\((x+y)^2 = x^2 + 2xy + y^2\)</span></li>
<li><span class="math inline">\((x+y)^3 = x^3 + 3x^2y + 3xy^2 +
y^3\)</span></li>
<li><span class="math inline">\((x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3
+ y^4\)</span></li>
</ul>
<h3 id="多项式定理">多项式定理</h3>
<p><strong>定义</strong>：多项式<span
class="math inline">\((x_1+x_2+\cdots+x_t)^n\)</span>的系数为：</p>
<p><span class="math display">\[\binom{n}{n_1,n_2,\cdots,n_t} =
\frac{n!}{n_1!n_2!\cdots n_t!}\]</span> 其中<span
class="math inline">\(n_1,n_2,\cdots,n_t\)</span>是非负整数，且<span
class="math inline">\(n_1+n_2+\cdots+n_t=n\)</span></p>
<p><strong>性质</strong>：</p>
<ol type="1">
<li><p>二项式系数可表示为：<span class="math inline">\(\binom{n}{k} =
\binom{n}{k,n-k}\)</span></p></li>
<li><p>帕斯卡公式：</p>
<ul>
<li>二项式：<span class="math inline">\(\binom{n}{k,n-k} =
\binom{n-1}{k,n-k-1} + \binom{n-1}{k-1,n-k}\)</span></li>
<li>多项式：<strong style="color:red"><span
class="math inline">\(\binom{n}{n_1,n_2,\cdots,n_t} = \sum_{i=1}^t
\binom{n-1}{n_1,\cdots,n_i-1,\cdots,n_t}\)</span></strong></li>
</ul></li>
</ol>
<p>设<span class="math inline">\(n\)</span>为正整数，对所有的<span
class="math inline">\(x_1,x_2,\cdots,x_t\)</span>，有：</p>
<p><span class="math display">\[(x_1+x_2+\cdots+x_t)^n = \sum
\frac{n!}{n_1!n_2!\cdots n_t!}x_1^{n_1}x_2^{n_2}\cdots
x_t^{n_t}\]</span> 其中求和是对所有满足<span
class="math inline">\(n_1+n_2+\cdots+n_t=n\)</span>的非负整数解进行的。</p>
<p><strong>例子</strong>：在<span
class="math inline">\((x_1+x_2+x_3+x_4+x_5)^7\)</span>的展开式中，<span
class="math inline">\(x_1^2x_3x_4^3x_5\)</span>的系数为<span
class="math inline">\(\binom{7}{2,0,1,3,1} = 420\)</span></p>
<p><strong>注</strong>：展开式中不同项的个数等于方程<span
class="math inline">\(n_1+n_2+\cdots+n_t=n\)</span>的非负整数解的个数，即<span
class="math inline">\(\binom{n+t-1}{n}\)</span></p>
<p>"选板法"： <span class="math inline">\(n + t-1\)</span> 个位置选
<span class="math inline">\(t-1\)</span> 个位置做挡板，剩下 <span
class="math inline">\(n\)</span> 个位置是 <span
class="math inline">\(1\)</span>，就相当于分成了 <span
class="math inline">\(t\)</span> 个区间，每个区间的 <span
class="math inline">\(1\)</span> 的个数是非负整数，<span
class="math inline">\(\binom{n+t-1}{n}=\binom{n+t-1}{t-1}\)</span>
。</p>
<h3 id="组合数递推">组合数递推</h3>
<p>根据帕斯卡公式以及杨辉三角对称性，熟练掌握组合数递推模板</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line">LL cm[maxn][maxn];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ComList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; maxn; i ++)</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt;= i; j ++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(j &gt; i - j) cm[i][j] = cm[i][i - j];</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(!j) cm[i][j] = <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span> cm[i][j] = j == <span class="number">1</span> ? i : cm[i - <span class="number">1</span>][j] + cm[i - <span class="number">1</span>][j - <span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="特殊计数序列科普">特殊计数序列科普</h2>
<h3 id="卡特兰数catalan-numbers">卡特兰数（Catalan Numbers）</h3>
<p><strong>应用场景</strong>：</p>
<ul>
<li><strong>括号匹配</strong>：<span
class="math inline">\(n\)</span>对括号有多少种合法的排列方式（任意前缀中左括号不少于右括号）</li>
<li><strong>找零问题</strong>：<span
class="math inline">\(n\)</span>个人拿50美分，<span
class="math inline">\(n\)</span>个人拿1美元，售票处总有零钱找的排队方式数</li>
<li><strong>网格路径</strong>：在<span
class="math inline">\(n×n\)</span>网格中从<span
class="math inline">\((0,0)\)</span>走到<span
class="math inline">\((n,n)\)</span>，不越过对角线的路径数</li>
<li><strong>三角剖分</strong>：凸多边形被在其内部<strong>不相交的对角线</strong>划分成三角形区域的方法数</li>
<li><strong>二叉树</strong>：<span
class="math inline">\(n\)</span>个节点能构成多少种不同的二叉树。</li>
</ul>
<p><strong>公式</strong>：</p>
<p>第<span class="math inline">\(n\)</span>个卡特兰数为：</p>
<p><span class="math display">\[
C_n = \frac{1}{n+1} \binom{2n}{n}, \quad C_0=1.
\]</span></p>
<p>例：找零问题<br />
<span
class="math inline">\(2n\)</span>个人排成一列进入剧场。入场费为50美分。其中<span
class="math inline">\(n\)</span>个人有50美分硬币，<span
class="math inline">\(n\)</span>个人有1美元纸币。有多少种排队方法使得每当有1美元的人买票时，售票处总有50美分硬币找零？</p>
<p>将50美分视为<span class="math inline">\(+1\)</span>，1美元视为<span
class="math inline">\(-1\)</span>，合法序列要求任意前缀和<span
class="math inline">\(\geq 0\)</span>，等价于括号匹配问题，答案为第<span
class="math inline">\(n\)</span>个卡特兰数：</p>
<p><strong>卡特兰数简要推导</strong>：</p>
<ol type="1">
<li>考虑所有可能的排列方式，总数为<span
class="math inline">\(\binom{2n}{n}\)</span></li>
<li>考虑不合法的情况（前缀和为负）
<ol type="1">
<li>对于每个不合法序列，找到第一个前缀和为-1的位置，将之前的所有数取反</li>
<li>这样得到“<span class="math inline">\(n+1\)</span>个<span
class="math inline">\(+1\)</span>和<span
class="math inline">\(n-1\)</span>个<span
class="math inline">\(-1\)</span>”的序列</li>
<li>不合法序列与这样的序列一一对应</li>
<li>因此不合法序列数为<span
class="math inline">\(\binom{2n}{n+1}\)</span>，即“<span
class="math inline">\(n+1\)</span>个<span
class="math inline">\(+1\)</span>和<span
class="math inline">\(n-1\)</span>个<span
class="math inline">\(-1\)</span>”</li>
</ol></li>
<li>合法序列数 = 总数 - 不合法数 = <span
class="math inline">\(\binom{2n}{n} - \binom{2n}{n+1} =
\frac{1}{n+1}\binom{2n}{n}\)</span></li>
</ol>
<h3
id="第二类斯特林数stirling-numbers-of-the-second-kind">第二类斯特林数（Stirling
Numbers of the Second Kind）</h3>
<p><strong>应用场景</strong>：</p>
<ul>
<li><strong>分组问题</strong>：将<span
class="math inline">\(p\)</span>个不同的物品分成<span
class="math inline">\(k\)</span>个<strong>不可区分</strong>的非空盒子（如划分集合）。</li>
<li><strong>等价关系</strong>：<span
class="math inline">\(p\)</span>个元素的集合划分为<span
class="math inline">\(k\)</span>个非空子集的方案数。</li>
</ul>
<p><strong>公式</strong>：</p>
<p>记作<span class="math inline">\(S(p,k)\)</span>，满足递推关系：</p>
<p><span class="math display">\[
S(p,k) = k \cdot S(p-1,k) + S(p-1,k-1),
\]</span><br />
初始条件：<span class="math inline">\(S(p,p)=1\)</span>, <span
class="math inline">\(S(p,0)=0\)</span>（<span class="math inline">\(p
\geq 1\)</span>）。</p>
<p><strong>例子</strong>：</p>
<ul>
<li><span
class="math inline">\(S(4,2)=7\)</span>：将4个物品分成2组的方案，如<span
class="math inline">\(\{1\}\{2,3,4\}\)</span>、<span
class="math inline">\(\{1,2\}\{3,4\}\)</span>等。</li>
</ul>
<h3 id="贝尔数bell-numbers">贝尔数（Bell Numbers）</h3>
<p><strong>应用场景</strong>：</p>
<ul>
<li><strong>集合划分总数</strong>：<span
class="math inline">\(p\)</span>个元素的集合所有可能的非空子集划分方式数（不限定子集数量）。</li>
</ul>
<p><strong>与斯特林数的关系</strong>：</p>
<p><span class="math display">\[
B_p = \sum_{k=0}^p S(p,k).
\]</span></p>
<p><strong>递推公式</strong>：</p>
<p><span class="math display">\[
B_p = \sum_{t=0}^{p-1} \binom{p-1}{t} B_t.
\]</span></p>
<p><strong>例子</strong>：</p>
<ul>
<li><span class="math inline">\(B_3=5\)</span>：对应划分：<span
class="math inline">\(\{1,2,3\}\)</span>、<span
class="math inline">\(\{1\}\{2,3\}\)</span>、<span
class="math inline">\(\{2\}\{1,3\}\)</span>、<span
class="math inline">\(\{3\}\{1,2\}\)</span>、<span
class="math inline">\(\{1\}\{2\}\{3\}\)</span>。</li>
</ul>
<h3
id="第一类斯特林数stirling-numbers-of-the-first-kind">第一类斯特林数（Stirling
Numbers of the First Kind）</h3>
<p><strong>应用场景</strong>：</p>
<ul>
<li><strong>循环排列</strong>：将<span
class="math inline">\(p\)</span>个物品排成<span
class="math inline">\(k\)</span>个非空的<strong>循环排列</strong>（如圆桌座位）。</li>
</ul>
<p><strong>递推公式</strong>：</p>
<p><span class="math display">\[
s(p,k) = (p-1) \cdot s(p-1,k) + s(p-1,k-1).
\]</span></p>
<p><strong>例子</strong>：</p>
<ul>
<li><span
class="math inline">\(s(4,2)=11\)</span>：将4个物品分成2个循环排列的方案，如<span
class="math inline">\((1\,2\,3)(4)\)</span>、<span
class="math inline">\((1\,3\,4)(2)\)</span>等。</li>
</ul>
<h3 id="大schroder数与小schroder数">大Schroder数与小Schroder数</h3>
<p><strong>应用场景</strong>：</p>
<ul>
<li><strong>格路径</strong>：从<span
class="math inline">\((0,0)\)</span>到<span
class="math inline">\((n,n)\)</span>的路径，允许水平、垂直和对角步（HVD），且不越过对角线（大Schroder数<span
class="math inline">\(R_n\)</span>）。</li>
<li><strong>加括号问题</strong>：对序列<span class="math inline">\(a_1
a_2 \cdots a_n\)</span>添加括号的方式数（小Schroder数<span
class="math inline">\(s_n\)</span>，允许括号包含多个元素）。</li>
</ul>
<img src="/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/%E6%A0%BC%E8%B7%AF%E5%BE%84.svg" class="">
<p><strong>关系</strong>：</p>
<p><span class="math display">\[
R_n = 2 s_{n+1} \quad (n \geq 1).
\]</span></p>
<p><strong>例子</strong>：</p>
<ul>
<li><span class="math inline">\(n=3\)</span>时，小Schroder数<span
class="math inline">\(s_3=3\)</span>：对应加括号方式为<code>a1(a2a3)</code>,
<code>(a1a2)a3</code>,
<code>a1a2a3</code>（注意与卡特兰数的区别）。</li>
</ul>
<h3 id="总结表格">总结表格</h3>
<table>
<colgroup>
<col style="width: 17%" />
<col style="width: 15%" />
<col style="width: 34%" />
<col style="width: 32%" />
</colgroup>
<thead>
<tr class="header">
<th>序列</th>
<th>记号</th>
<th>应用场景</th>
<th>前几项（从<span class="math inline">\(n=0\)</span>）</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>卡特兰数</td>
<td><span class="math inline">\(C_n\)</span></td>
<td>括号匹配、路径不越对角线</td>
<td>1, 1, 2, 5, 14, 42</td>
</tr>
<tr class="even">
<td>第二类斯特林</td>
<td><span class="math inline">\(S(p,k)\)</span></td>
<td>集合划分到<span class="math inline">\(k\)</span>个子集</td>
<td><span class="math inline">\(S(3,2)=3\)</span></td>
</tr>
<tr class="odd">
<td>贝尔数</td>
<td><span class="math inline">\(B_p\)</span></td>
<td>集合所有划分方式</td>
<td>1, 1, 2, 5, 15, 52</td>
</tr>
<tr class="even">
<td>第一类斯特林</td>
<td><span class="math inline">\(s(p,k)\)</span></td>
<td>循环排列数</td>
<td><span class="math inline">\(s(4,2)=11\)</span></td>
</tr>
<tr class="odd">
<td>大Schroder数</td>
<td><span class="math inline">\(R_n\)</span></td>
<td>HVD格路径</td>
<td>1, 2, 6, 22, 90</td>
</tr>
<tr class="even">
<td>小Schroder数</td>
<td><span class="math inline">\(s_n\)</span></td>
<td>广义加括号方式</td>
<td>1, 1, 3, 11, 45</td>
</tr>
</tbody>
</table>
<p>使用技巧：<strong style="color:red">准备常用数列表，遇事不决暴力打表，人工观察找规律</strong></p>
<h2 id="nim-游戏">Nim 游戏</h2>
<ul>
<li><p><strong>游戏设置</strong>：有 $ k $ 堆硬币，每堆分别有 $ n_1,
n_2, , n_k $ 枚硬币。</p></li>
<li><p><strong>玩家轮流取子</strong>：</p>
<ul>
<li>玩家 I（先手）和玩家 II（后手）交替进行。</li>
<li>每次从<strong>某一堆</strong>中取走<strong>至少一枚</strong>硬币。</li>
</ul></li>
<li><p><strong>胜负判定</strong>：取走<strong>最后一枚硬币</strong>的玩家获胜。</p></li>
</ul>
<h3 id="堆-nim-游戏的策略">2 堆 Nim 游戏的策略</h3>
<ul>
<li><p><strong>关键观察</strong>：若两堆硬币数不等（$ n_1 n_2 $），玩家
I 必胜；否则玩家 II 必胜。</p></li>
<li><p><strong>必胜策略</strong>：</p>
<ol type="1">
<li>玩家 I 从较多的堆中取硬币，使两堆数量<strong>相同</strong>。</li>
<li>之后，玩家 I <strong>模仿玩家 II 的操作</strong>：若玩家 II 从一堆取
$ c $ 枚，玩家 I 从另一堆取 $ c $ 枚。</li>
</ol></li>
<li><p><strong>示例</strong>：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">初始状态：(8, 5)</span><br><span class="line">玩家 I 取 3 → (5, 5)      // 使两堆相同</span><br><span class="line">玩家 II 取 2 → (5, 3)</span><br><span class="line">玩家 I 取 2 → (3, 3)      // 模仿对手</span><br><span class="line">玩家 II 取 1 → (3, 2)</span><br><span class="line">玩家 I 取 1 → (2, 2)      // 继续模仿</span><br><span class="line">...</span><br><span class="line">玩家 I 取走最后一枚硬币获胜。</span><br></pre></td></tr></table></figure></li>
</ul>
<hr />
<h3 id="通用-k--堆-nim-游戏的策略">通用 $ k $-堆 Nim 游戏的策略</h3>
<ul>
<li><p><strong>二进制表示</strong>：将每堆硬币数 $ n_i $
表示为二进制，例如 $ 53 = 110101_2 $。</p></li>
<li><p><strong>平衡状态</strong>：对于所有二进制位，统计所有堆在该位上为
1 的总数。若<strong>所有位总数均为偶数</strong>，则游戏平衡。</p></li>
<li><p><strong>胜负判定</strong>：</p>
<ul>
<li><strong>非平衡状态</strong>：玩家 I
必胜，可通过一步操作使游戏平衡。</li>
<li><strong>平衡状态</strong>：玩家 II 必胜。</li>
</ul></li>
<li><p><strong>必胜策略</strong>：</p>
<ol type="1">
<li>找到<strong>最高不平衡位</strong>（即 1
的总数为奇数的最高位）。</li>
<li>选择一个该位为 1
的堆，调整其硬币数，使得各个位的总数均变为偶数。</li>
<li>对手的任何操作都会破坏平衡，玩家 I 可重复此策略直至获胜。</li>
</ol></li>
</ul>
<img src="/2025-06-18-36-%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E5%85%A5%E9%97%A8/nim%E6%B8%B8%E6%88%8F_k%E5%A0%86.svg" class="">
<p>尝试：</p>
<ul>
<li><p><strong>堆大小</strong>：10, 20, 30, 40, 50。</p></li>
<li><p><strong>二进制表示</strong>：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">10: 001010</span><br><span class="line">20: 010100</span><br><span class="line">30: 011110</span><br><span class="line">40: 101000</span><br><span class="line">50: 110010</span><br></pre></td></tr></table></figure></li>
<li><p><strong>位统计</strong>（从右到左，位 0 开始）：</p>
<ul>
<li>位 1: 总数 = 3（非平衡）</li>
<li>位 4: 总数 = 3（非平衡）</li>
<li></li>
</ul></li>
<li><p><strong>玩家 I 的操作</strong>：</p>
<ol type="1">
<li>选择最高非平衡位（位 4），并选中该位为 1 的堆（如 50）。</li>
<li>将 50 调整为 $ 50 = 50 (10 ) = 40 $。</li>
<li>需从 50 中取走 $ 50 - 40 = 10 $ 枚，使堆变为 40。</li>
</ol></li>
<li><p><strong>验证平衡</strong>：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">调整后堆：10, 20, 30, 40, 40</span><br><span class="line">二进制统计：  </span><br><span class="line"></span><br><span class="line"></span><br><span class="line">位 0-5 的 1 总数均为偶数 → 游戏平衡。</span><br></pre></td></tr></table></figure>
<p>此后，玩家 II 的任何操作都会破坏平衡，玩家 I
可维持策略获胜。</p></li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/ACM/" rel="tag"># ACM</a>
              <a href="/tags/Algorithm/" rel="tag"># Algorithm</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2025-06-11-35-%E6%95%B0%E8%AE%BA%E5%85%A5%E9%97%A8/" rel="prev" title="35.数论入门">
                  <i class="fa fa-angle-left"></i> 35.数论入门
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2025-06-25-37-%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E5%85%A5%E9%97%A8/" rel="next" title="37.计算几何入门">
                  37.计算几何入门 <i class="fa fa-angle-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments utterances-container"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">

  <div class="copyright">
    &copy; 
    <span itemprop="copyrightYear">2025</span>
    <span class="with-love">
      <i class="fa fa-heart"></i>
    </span>
    <span class="author" itemprop="copyrightHolder">CSGrandeur</span>
  </div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://fastly.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://fastly.jsdelivr.net/npm/@next-theme/pjax@0.6.0/pjax.min.js" integrity="sha256-vxLn1tSKWD4dqbMRyv940UYw4sXgMtYcK6reefzZrao=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/sidebar.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  <script src="https://fastly.jsdelivr.net/npm/hexo-generator-searchdb@1.4.1/dist/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>







  




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://fastly.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


<script class="next-config" data-name="utterances" type="application/json">{"enable":true,"repo":"CSGrandeur/csgrandeur.github.io","issue_term":"pathname","theme":"github-light"}</script>
<script src="/js/third-party/comments/utterances.js"></script>

</body>
</html>
